package leetcode_700;

/**
 *@author 周杨
 *NumberOfLongestIncreasingSubsequence_673 计算一个数组 最长增子序列的数量
 *describe:用动态规划 AC 57%	
 *2018年10月5日 下午5:37:07
 */
public class NumberOfLongestIncreasingSubsequence_673 {
	public static void main(String[] args) {
		NumberOfLongestIncreasingSubsequence_673 test=new NumberOfLongestIncreasingSubsequence_673();
		//test.findNumberOfLIS(new int[] {1,3,5,4,7});
		System.out.println(test.findNumberOfLIS(new int[] {2,2,2,2,2}));
	}
	
	public int findNumberOfLIS(int[] nums) {
		if (nums == null || nums.length == 0) return 0;

        int[] mostLongestContainMe = new int[nums.length], times = new int[nums.length];

        int mostLongest = 1, total = 0;//定义全局变量
        for (int i = 0; i < nums.length; ++i) {
            int time = 1, max = 0;
            for (int j = i - 1; j >= 0; --j) {
                if (nums[j] < nums[i]) {
                    if (mostLongestContainMe[j] > max) {//max是这次里面最长的子序列
                        max = mostLongestContainMe[j];
                        time = times[j];
                    } else if (mostLongestContainMe[j] == max) {//如果有相等的 则累加计数
                        time += times[j];
                    }
                }
            }
            times[i] = time;
            mostLongestContainMe[i] = max + 1;//遍历完所有的
            if (mostLongestContainMe[i] > mostLongest) {
                mostLongest = mostLongestContainMe[i];
                total = times[i];
            } else if (mostLongestContainMe[i] == mostLongest) total += times[i];
        }

        return total;
    }
}
